// cf-392c
// 题意：给定fibonacci数列f[i]，然后定义A[i](k)为f[i]*i^k。
//       给定n(<=10^17), k(<=40)求A[1](k)+A[2](k)+...+A[n](k)。
//       答案模10^9+7。
//
// 题解：其实这道题并不难。推出A[i](k)的公式为：
//         A[i](k)=sigma(A[i-1](j)*C(k, j), j=0 to k) + 
//                 sigma(A[i-2](j)*C(k, j)*2^(k-j), j=0 to k)
//       因为k很小，所以就可以弄个(2*k+3)*(2*k+3)大小的矩阵，
//       把递推维护出来，最后在维护和就行。
//
// run: $exec < input
#include <iostream>
#include <vector>

long long constexpr mod = 1000000007;

struct matrix
{
	using value_type = long long;
	using row_type = std::vector<value_type>;

	matrix(int ro, int co)
	{
		mat.resize(ro);
		for (auto & i : mat) i.resize(co);
	}

	matrix(int n) : matrix(n, n)
	{
		for (int i = 0; i < n; i++) mat[i][i] = 1;
	}

	matrix() = default;

	int row() const { return mat.size(); }
	int col() const { return mat[0].size(); }

	row_type       & operator[](int x)       { return mat[x]; }
	row_type const & operator[](int x) const { return mat[x]; }

	private:
	std::vector<row_type> mat;
};

matrix operator*(matrix const & a, matrix const & b)
{
	int n = a.row(), m = b.col(), t = a.col();
	matrix r(n, m);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < t; k++)
				r[i][j] = (r[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
	return r;
}

matrix quick_pow(matrix const & a, long long b)
{
	if (!b) return matrix(a.row());

	matrix ret = quick_pow(a, b / 2);
	ret = ret * ret;
	if (b & 1) ret = ret * a;
	return ret;
}

long long c[50][50];
long long pow2[50];

void init()
{
	c[0][0] = 1;
	for (int i = 1; i < 50; i++) {
		c[i][0] = 1;
		for (int j = 1; j <= i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	}
	pow2[0] = 1;
	for (int i = 1; i < 50; i++)
		pow2[i] = (pow2[i - 1] * 2) % mod;
}

int main()
{
	std::ios::sync_with_stdio(false);
	init();
	long long n, k;
	std::cin >> n >> k;
	if (n == 1) { std::cout << "1\n"; return 0; }
	matrix a(2 * k + 3, 2 * k + 3);
	for (int i = 0; i <= k; i++) {
		for (int j = 0; j <= i; j++)
			a[i][j] = c[i][j];
		for (int j = 0; j <= i; j++)
			a[i][j + k + 1] = (c[i][j] * pow2[i - j]) % mod;
	}
	for (int i = 0; i <= k; i++)
		a[i + k + 1][i] = 1;
	a[2 * k + 2][2 * k + 2] = 1;
	for (int j = 0; j <= k; j++) {
		a[2 * k + 2][j] = c[k][j];
		a[2 * k + 2][j + k + 1] = (c[k][j] * pow2[k - j]) % mod;
	}

	matrix init(2 * k + 3, 1);
	for (int i = 0; i <= k; i++) {
		init[i][0] = pow2[i + 1];
		init[k + i + 1][0] = 1;
	}
	init[2 * k + 2][0] = (pow2[k + 1] + 1) % mod;
	a = quick_pow(a, n - 2);
	init = a * init;
	std::cout << init[2 * k + 2][0] << '\n';
}

